package algorithm.primary.dfs;

import com.sun.xml.internal.fastinfoset.stax.factory.StAXOutputFactory;
import org.junit.Test;

/**
 * @author Summerday
 */
public class DFS {


    int n = 4, k = 13;
    int[] a = new int[]{1,2,4,7};

    boolean dfs(int i , int sum){
        //已经从前i项得到了和sum,
        if(i == n) return sum == k;

        // 不加a[i] 的情况
        if(dfs(i + 1, sum)) return true;

        // 加a[i]的情况
        if(dfs(i + 1 , sum + a[i])) return true;
        return false;
    }

    @Test
    public void solve(){
        if(dfs(0, 0)) System.out.println("yes");
        else System.out.println("no");
    }


}
